package main

import "fmt"

/**
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5
Output: 2

Example 2:

Input: [1,3,5,6], 2
Output: 1

Example 3:

Input: [1,3,5,6], 7
Output: 4

Example 1:

Input: [1,3,5,6], 0
Output: 0
*/

// 暴力破解 时间复杂度O(n)
func searchInsertSolutionOne(nums []int, target int) int {
	length := len(nums)

	if length == 0 {
		return 0
	}

	for i := 0; i < length; i++ {
		if nums[i] == target || nums[i] > target {
			return i
		}
	}

	return length
}

// 二分查找 时间复杂度O(logn)
func searchInsertSolutionTwo(nums []int, target int) int {
	left, right := 0, len(nums)-1
	for left <= right {
		m := left + (right-left)/2
		if nums[m] == target {
			return m
		} else if target > nums[m] {
			left = m + 1
		} else {
			right = m - 1
		}
	}

	return right + 1
}

//循环结束时，一定有 right < left，并且 left 正好落在插入位置，left=right+1

func main() {
	fmt.Print(searchInsertSolutionTwo([]int{1, 2, 3, 5}, 4))
}
